//
// Created by hamlet on 23-2-25.
//

#include "Solver.h"
#include <climits>
#include <QDebug>

Solver::Solver(const QString &w1, const QString &w2)
        : word1(w1), word2(w2),
          distance(w1.size() + 1, QVector<int>(w2.size() + 1, INT_MAX)),
          direction(w1.size() + 1, QVector<Op>(w2.size() + 1, Op::UNKNOWN)) {
    cost[Op::INSERTION] = 1;
    cost[Op::DELETION] = 1;
    cost[Op::SUBSTITUTION] = 1;
    cost[Op::NO_CHANGE] = 0;
}

void Solver::solve() {
    distance[0][0] = 0;
    for (int i = 1; i <= word1.size(); ++i) {
        distance[i][0] = distance[i - 1][0] + cost[Op::DELETION];
        direction[i][0] = Op::DELETION;
    }
    for (int i = 1; i <= word2.size(); ++i) {
        distance[0][i] = distance[0][i - 1] + cost[Op::INSERTION];
        direction[0][i] = Op::INSERTION;
    }
    for (int i = 1; i <= word1.size(); ++i) {
        for (int j = 1; j <= word2.size(); ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                distance[i][j] = distance[i - 1][j - 1] + cost[Op::NO_CHANGE];
                direction[i][j] = Op::NO_CHANGE;
            } else {
                int d1 = distance[i - 1][j] + cost[Op::DELETION];
                int d2 = distance[i][j - 1] + cost[Op::INSERTION];
                int d3 = distance[i - 1][j - 1] + cost[Op::SUBSTITUTION];
                if (d1 < d2 && d1 < d3) {
                    distance[i][j] = d1;
                    direction[i][j] = Op::DELETION;
                } else if (d2 < d3) {
                    distance[i][j] = d2;
                    direction[i][j] = Op::INSERTION;
                } else {
                    distance[i][j] = d3;
                    direction[i][j] = Op::SUBSTITUTION;
                }
            }
        }
    }
}

QList<Solver::Point> Solver::backtrace() {
    QList<Point> bt;
    int i = word1.size(), j = word2.size();
    Op dir = Op::UNKNOWN;
    while (i > 0 || j > 0) {
        bt.push_front({dir, i, j});
        dir = direction[i][j];
        switch (dir) {
            case Op::INSERTION:
                j -= 1;
                break;
            case Op::DELETION:
                i -= 1;
                break;
            case Op::SUBSTITUTION:
            case Op::NO_CHANGE:
                i -= 1, j -= 1;
                break;
            case Op::UNKNOWN:
                break;
        }
    }
    bt.push_front({dir, 0, 0});
    return std::move(bt);
}
